1. Field of the Invention
This invention relates to a pattern reading system adapted for the recognition of characters, particularly handprinted characters.
2. Description of the Prior Art
In the past, as systems for recognizing hand-printed characters have had no accepted standard forms, the structural analysis approach has been used most widely. In this approach, the local characteristic properties of the visual patterns of characters to be recognized are extracted, each of the characters is represented by a construction composed of the extracted features, and the construction is recognized. The known methods may be broadly divided into two types as follows:
a) Methods based on the recognition that each character is made up of lines and the character is recognized on the basis of these line elements.
b) Methods in which each character made up of the black portion is recognized by extracting the geometric features of the character including the white background portion.
Methods of type a) usually require a preliminary processing or thinning procedure whereby the line segments of the resulting thin character are extracted and approximated with straight lines. These methods have the disadvantages of confusing the features of a character due to the occurrence of xe2x80x9cwhiskersxe2x80x9d and the loss of the delicate shapes of the character caused by the thinning operation. Another disadvantage is the fact that the approximation of curves with broken lines tends to complicate the representation of the curves. These disadvantages impose some limitations on the methods of the above a).
In contrast, the methods of type b) are effective in that the features of a character including the white background portion can be extracted without any thinning operation and the concavity and convexity of the line segments of the character are extracted only by following the contours.
Many different techniques have-been developed for performing these methods but these techniques have been disadvantageous from the hardware point of view. For example, in the case of the method in which the concave and convex segments of a character are extracted by a two-dimensional processor in accordance with a two-dimensional parallel processing, the construction of the required apparatus will inevitably be extremely complicated and the cost will also be large. In the case of the other method, which is designed to overcome these deficiencies and in which a specially designed one-dimensional processor is used to process data line by line, there is a disadvantage that, since the method is based on line parallel processing, it is necessary to use a special processor for speeding up the processing. Moreover, a character consisting of discrete line segments cannot be positively recognized unless sufficient continuity of the respective points is maintained, thus inevitably complicating the apparatus.
To avoid these shortcomings, character recognition systems capable of highly accurate character recognition, and having a number of advantages from the hardware point of view, have been developed, in which the contour of a character is traced to extract the individual concave and convex line segments on the contour. This tracing procedure has the advantage of a reduced number of calculation points, because the number of points on a contour is far fewer than the number of points in the entire, 2-dimensional memory. For example, the ratio of the number na of intersections on the entire two-dimensional memory to the number nb of the points on the contour of a character would typically be on the order of 20. Therefore, the number of calculation points to be processed would be reduced to about one twentieth by using the contour technique. Other advantages are that no preliminary processing is required for extracting the connected components and the sequence of all the calculation points, or their connections forming the line segments, is defined, making it easier to determine the correspondence of the extracted features for a matching operation with a dictionary.
However, this tracing system has the disadvantage of being unsuited for use with two-dimensional parallel processing. Also, the concavity and convexity structure extraction systems known to date, which employ this tracing technique, are disadvantageous in that the recognition, though exact, inevitably tends to become microscopic; while there will be no problem in the case of a character with a smooth boundary surface, the presence of a large number of small concave and convex segments on the contour can cause a convex line segment to be mistaken for a concave line segment and so on.
With the purpose of overcoming the foregoing deficiencies in the prior art, it is a main object of the present invention to provide a pattern reading system in which, without being affected by the local variations, particularly the small concave and convex segments on the contour of a character pattern, the contour is segmented on the basis of a global feature extraction and then the detailed parameters of feature are extracted so as to perform the pattern reading.
It is another object of the invention to provide a pattern reading system in which the preparation of a dictionary for effecting the reading is accomplished in such a manner that the short convex line segments are rejected and the arrangement of the line segments is controlled for a matching operation, thereby making the dictionary compact without any deterioration in the pattern recognition performance.
In accordance with the pattern reading system of this invention, a two-dimensional memory stores a two-dimensional character pattern of a character which was scanned by an optical scanner and the stored content is recognized with a high efficiency by a recognition system based on the xe2x80x9coutermost point method.xe2x80x9d More specifically, while tracing the contour of the two-dimensional character pattern on the two-dimensional memory, the distances of the traced points on the contour from the starting point of the tracing are obtained and simultaneously the integrated values of the coordinates of the traced points on the contour from the starting point are calculated so as to extract them as outermost points for the series of contours. Then, in accordance with the outermost points, the character contours are segmented into the convex line segments, concave line segments and hole segments and then the parameters of feature are detected for each of the segments. Convex line segments which are shorter than a predetermined length are rejected and the remaining segments are subjected to a matching operation with the preliminarily prepared dictionary, thereby recognizing the two-dimensional pattern.
In extracting the parameters of the geometrical features of the segments, henceforth referred to as the xe2x80x9cfeature parametersxe2x80x9d of the segments, the feature parameters of the first concave line segment detected, and the feature parameters of the other segments, are grouped in the order of detection as the first-category features. Also the feature parameters of segments ranging from the second concave line segment in said group up to the segment next to the first concavity line segment are sequentially grouped as the second-category features, thereby providing an alternative, ordered group with a different starting angle. When there is a specific designation in the dictionary, a match is attempted between the two sets of the feature parameters and the dictionary, thereby accomplishing the two-dimensional pattern recognition.
In accordance with the invention, the recognition of patterns with a high degree of accuracy can still be ensured even if the memory capacity of the dictionary is reduced and there is no need to use an additional dictionary for considerably distorted forms of the input character. Moreover, a decision can be automatically made regarding the identity of the input character by means of the feature parameters representing the partial patterns, without using any specially designed processor, and the character-at-a-time processing ensures an effective recognition of a visual pattern which is in the form of a discrete pattern. Further, there is no need to increase the memory capacity, and even characters which are deformed more or less can be read effectively, thus making it possible to realize a pattern recognition apparatus which is well suited for automatic reading of handprinted characters.
The invention will be described in greater detail with reference to the accompanying drawings.